Number of longest increasing subsequence

Time: O(N^2); Space: O(N); medium

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: nums = [1,3,5,4,7] Output: 2

Explanation:

  • The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: nums =[2,2,2,2,2]

Output: 5

Explanation:

  • The length of longest continuous increasing subsequence is 1, and there are 5 subsequences’ length is 1, so output 5.

Constraints:

  • Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

[1]:

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result, max_len = 0, 0
        dp = [[1, 1] for _ in range(len(nums))]  # {length, number} pair
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[i][0] == dp[j][0]+1:
                        dp[i][1] += dp[j][1]
                    elif dp[i][0] < dp[j][0]+1:
                        dp[i] = [dp[j][0]+1, dp[j][1]]
            if max_len == dp[i][0]:
                result += dp[i][1]
            elif max_len < dp[i][0]:
                max_len = dp[i][0]
                result = dp[i][1]
        return result



[2]:

s = Solution1()

nums = [1,3,5,4,7]
assert s.findNumberOfLIS(nums) == 2

nums = [2,2,2,2,2]
assert s.findNumberOfLIS(nums) == 5